package 完全背包

/*
*
原题链接:
https://leetcode.cn/problems/word-break/

139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
	注意，你可以重复使用字典中的单词。

示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

思路: 转换为背包问题,使用字典中的物品,设法组成目标字符串

一. dp数组含义
	- dp[j]: 长度为j的字符串, 是否可以拆分为一个或多个在字典中出现的单词

二. 递推公式
	- 如果确定 dp[j]是true, 且[j,i]这个区间的子串出现在字典里, 那么dp[i]一定是true. (j<i)
	所以递推公式是 if(j,i)这个区间的子串出现在字典里 && dp[j]为true, 那么dp[i]=true

三. dp数组如何初始化
	dp[0] = true	dp[0]表示如果字符串为空,说明在字典中.  并且如果dp[0]一旦初始化为false, 那么后续的递推结果全都是false了

四. 确定遍历顺序
	- 本题求得是排列数.
		拿s = "applepenapple", wordDict=["apple", "pen"]举例
		"apple", "pen"是物品, 那么我们要求物品得组合一定是 "apple" + "pen" + "apple"才能组成 "applepenapple"
		"apple" + "apple" + "pen"或者"pen" + "apple" + "apple"是不可以的,
		那么我们就是强调物品之间顺序.

	所以说, 本题一定是先遍历背包, 再遍历物品

五. 打印dp数组
*/
// 转化为 求装满背包s的前几位字符的方式有几种
func wordBreak(s string, wordDict []string) bool {
	// 装满背包s的前几位字符的方式有几种
	dp := make([]int, len(s)+1) //dp[i]: 拼接以i结尾的字符串, 有dp[i]种方法凑成
	dp[0] = 1

	for i := 0; i <= len(s); i++ { // 背包容量
		for j := 0; j < len(wordDict); j++ { // 物品
			//如果背包容量>=当前物品的长度 &&  当前物品==s[i-当前物品长度],  才有进行递推公式的必要
			if i >= len(wordDict[j]) && wordDict[j] == s[i-len(wordDict[j]):i] {
				dp[i] += dp[i-len(wordDict[j])] //那么当前dp[i] += 前面dp[j]位置的数量
			}
		}
	}

	return dp[len(s)] > 0
}
